package cn.zzf.leetcode;

/**
 * <pre>{@code
 * 给你一个链表数组，每个链表都已经按升序排列。
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 * 示例 1：
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下：
 * [
 * 1->4->5,
 * 1->3->4,
 * 2->6
 * ]
 * 将它们合并到一个有序链表中得到。
 * 1->1->2->3->4->4->5->6
 *
 * 示例 2：
 * 输入：lists = []
 * 输出：[]
 *
 * 示例 3：
 * 输入：lists = [[]]
 * 输出：[]
 *
 * 提示：
 * k == lists.length
 * 0 <= k <= 10^4
 * 0 <= lists[i].length <= 500
 * -10^4 <= lists[i][j] <= 10^4
 * lists[i] 按 升序 排列
 * lists[i].length 的总和不超过 10^4
 * }</pre>
 *
 * @author zzf
 */
public class T0023_MergeKLists {
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0)
            return null;
        if (lists.length == 1)
            return lists[0];
        ListNode result = new ListNode(-10001);
        ListNode resultNode = new ListNode();

        int minIdx = 0;
        int min = 10001;
        // int secondMin = 10002;


        while (true) {

            for (int i = 0; i < lists.length; i++) {
                ListNode current = lists[i];
                if (current == null)
                    continue;

                if (current.val <= min) {
                    //                    secondMin = min;
                    min = current.val;
                    minIdx = i;
                }/* else if (current.val <= secondMin) {
                    secondMin = current.val;
                }*/
            }
            if (min > 10000) {
                break;
            }
            // if (secondMin > 10000) {
            //     break;
            // }

            ListNode minNode = lists[minIdx];

            ListNode tmp = new ListNode();
            tmp.val = minNode.val;

            if (result.next == null) {
                resultNode = tmp;
                result.next = resultNode;
            } else {
                resultNode.next = tmp;
                resultNode = tmp;
            }

            lists[minIdx] = minNode.next;

            min = 10001;
            //            secondMin = 10002;
        }
        return result.next;
    }




}
